#ifndef XOR_H_
#define XOR_H_

#include <climits>
#include <cstddef>
#include <cstdint>
#include <string>
#include <type_traits>
#include <utility>
#include <vector>


namespace lxj
{

inline std::string getNumBinary(int a)
{
    std::string binary;
    binary.reserve(32);
    for (int i = 31; i >= 0; i--) {
        char c = ((a & (1 << i)) != 0) ? '1' : '0';
        binary.push_back(c);
    }
    return binary;
}

/*
    袋子里一共有a个白球，b个黑球每次从袋子里拿出2个球，每个球被拿出的机会均等
    如果每次从袋子里拿出2个白球，或2个黑球，那么重新将1个白球放回袋中
    如果每次从袋子里拿出1个白球，一个黑球，那么重新将1个黑球放回袋中
    那么最终袋子里一定会剩下1个球，这个球是黑球的概率是多少，用a和b表示
*/
// 其实这个题是陷阱题，和a无关
// 如果袋子中黑球的数量是偶数个，则最终球是黑色概率为 0%--false
// 如果是奇数个，则最终球是黑色概率为 100%--true
inline constexpr bool black_probability(size_t a, size_t b)
{
    return b % 2 == 0 ? false : true;
}

// 不用临时变量，交换两个数,不推荐使用
// a和b的内存地址不能相同，否则会将此内存地址中的值刷为0
template<class T, std::enable_if_t<std::is_arithmetic_v<T>, int> = 0>
void swap(T& a, T& b)
{
    if (a == b) return;
    a = a ^ b;
    b = a ^ b;
    a = a ^ b;
}

// 需要保证n==0 || n==1
inline int32_t flip(int32_t n)
{
    return n ^ 1;
}

// 非负数返回1，负数返回0
inline int32_t sign(int32_t n)
{
    return flip(n >> 31 & 1);
}

// 不用任何判断和比较操作，返回两个数的最大值
// 有溢出风险
inline int32_t max1(int32_t a, int32_t b)
{
    int32_t signa = sign(a - b);
    int32_t signb = sign(b - a);

    int32_t c = signa * a + signb * b;
    return c;
}

// 无溢出风险版
inline int32_t max2(int32_t a, int32_t b)
{
    int32_t c  = a - b;
    int32_t sa = sign(a);
    int32_t sb = sign(b);
    int32_t sc = sign(c);

    int32_t diffAB = sa ^ sb;
    int32_t sameAB = flip(diffAB);

    int32_t returnA = diffAB * sa + sameAB * sc;
    int32_t returnB = flip(returnA);

    return returnA * a + returnB * b;
}

// 268. 丢失的数字
// 给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。
inline int missingNumber(std::vector<int>& nums)
{
    int eorAll = 0;
    int eorHas = 0;
    for (int i = 0; i < nums.size(); i++) {
        eorAll ^= i;
        eorHas ^= nums[i];
    }
    eorAll ^= nums.size();

    return eorAll ^ eorHas;
}

// 136. 只出现一次的数字
/*
给你一个 非空 整数数组 nums
，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。
*/
inline int singleNumber1(std::vector<int>& nums)
{
    int eorAll = 0;
    for (auto i : nums) {
        eorAll ^= i;
    }
    return eorAll;
}

// 137. 只出现一次的数字 II
/*
给你一个整数数组 nums ，除某个元素仅出现 <m 外，其余每个元素都恰出现 m次 。
请你找出并返回那个只出现了m的元素。
你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。
*/

inline int singleNumber2(std::vector<int>& nums, int m)
{
    int cnt[32] = {};
    for (auto i : nums) {
        for (int k = 0; k < 32; k++) {
            cnt[k] += i >> k & 1;
        }
    }

    int ans = 0;
    for (int i = 0; i < 32; i++) {
        cnt[i] % m == 0 ? (int)0 : ans |= (1 << i);
    }
    return ans;
}

// 260. 只出现一次的数字 III
/* 给你一个整数数组 nums，其中恰好有两个元素只出现奇数次，其余所有元素均出现偶数次。
找出只出现奇数次的那两个元素。你可以按任意顺序返回答案。
你必须设计并实现线性时间复杂度的算法且仅使用常量额外空间来解决此问题。
*/
inline std::pair<int, int> singleNumber3(std::vector<int>& nums)
{
    // 提取数字n的二进制状态下最右侧的1
    auto Brain_Kernighan = [](int n) { return n & (-n); };
    int  eor1 = 0, eor2 = 0;
    for (auto i : nums) {
        eor1 ^= i;
    }

    int right_1 = eor1 == INT_MIN ? eor1 : eor1 & (-eor1);
    for (auto i : nums) {
        (i & right_1) == 0 ? eor2 ^= i : (int)0;
    }
    return std::make_pair(eor1 ^ eor2, eor2);
}

}   // namespace lxj

#endif